/*******************************************************************************
* FileName:         Graph.cpp
* Author:           李智铭
* Student Number:   3022206093
* Date:             2024/11/27 17:00:00
* Version:          v1.0
* Description:      Data Structure Experiment #10
*******************************************************************************/
#include "Graph.h"
#include "limits.h"
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

Graph::Graph(int max_v): 
    max_count(max_v), adjmax(max_v + 1, vector<int>(max_v + 1, INT_MAX)) {}

Graph::~Graph(){
    //STL容器自动管理内存，不需要手动delete
}

void Graph::addedge(int s, int t, int w){
    // 不允许环的出现
    if(s == t){
        cout << "a loop node is not allowed in this graph" << endl;
        return;
    }
    adjmax[s][t] = w; //直接赋值
}

int Graph::getInDegree(int v){
    int in_count = 0;
    for(int i = 1 ; i <= max_count ; i++){
        if(adjmax[i][v] != INT_MAX) in_count++; //遍历列
    }
    return in_count;
}

int Graph::getOutDegree(int v){
    int out_count = 0;
    for(int i = 1 ; i <= max_count ; i++){
        if(adjmax[v][i] != INT_MAX) out_count++; //遍历行
    }
    return out_count;
}

int Graph::access(int s, int t){
    if(adjmax[s][t] == INT_MAX) return -1; //不存在该边
    else return adjmax[s][t];
}

// 使用BFS
int Graph::getDist(int s, int t) {
    // 如果起点和终点相同，距离为 0
    if (s == t) return 0;

    // 初始化队列和访问标记数组
    vector<bool> visited(max_count + 1, false);
    vector<int> dist(max_count + 1, INT_MAX); // 存储到各节点的最短路径长度
    queue<int> q;

    // 起点入队
    q.push(s);
    visited[s] = true;
    dist[s] = 0;

    while (!q.empty()) {
        int curr = q.front();
        q.pop();

        // 遍历所有邻接点
        for (int i = 1; i <= max_count; ++i) {
            if (adjmax[curr][i] != INT_MAX && !visited[i]) { // 存在边且未访问
                q.push(i);
                visited[i] = true;
                dist[i] = dist[curr] + 1; // 路径长度 +1
                
                // 如果找到目标节点，直接返回距离
                if (i == t) return dist[i];
            }
        }
    }

    // 如果 BFS 完成后仍未找到目标节点，返回 -1 表示不可达
    return -1;
}
